package argo.hot100;

import java.util.*;

public class ThreeSum {

    public List<List<Integer>> threeSumOld(int[] nums) {
        int base = 0, left = 1, right = nums.length - 1;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        Set<String> set = new HashSet<>();
        while (base < nums.length - 2) {
            left = base + 1;
            right = nums.length - 1;
            while (left < right) {
                if (nums[right] + nums[left] + nums[base] > 0) {
                    right--;
                } else if (nums[right] + nums[left] + nums[base] < 0) {
                    left++;
                } else {
                    if (!set.contains("" + nums[base] + nums[left] + nums[right])) {
                        set.add("" + nums[base] + nums[left] + nums[right]);
                        ArrayList<Integer> subres = new ArrayList<>();
                        subres.addAll(Arrays.asList(nums[base], nums[left], nums[right]));
                        res.add(subres);
                    }
                    left++;
                    right--;
                }
            }
            base++;
        }

        return res;
    }


    public List<List<Integer>> threeSum(int[] nums) {
        int base = 0, left = 1, right = nums.length - 1;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        while (base < nums.length - 2) {
            while (base > 0 && base < nums.length - 2 && nums[base] == nums[base - 1]) {
                base++;
            }
            left = base + 1;
            right = nums.length - 1;
            while (left < right) {

                if (nums[right] + nums[left] + nums[base] > 0) {
                    right--;
                } else if (nums[right] + nums[left] + nums[base] < 0) {
                    left++;
                } else {
                    ArrayList<Integer> subres = new ArrayList<>();
                    subres.addAll(Arrays.asList(nums[base], nums[left], nums[right]));
                    res.add(subres);
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;
                }
            }
            base++;
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new ThreeSum().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}
